package com.shu.leetcode;


/**
 * @author ssm
 * @version V1.0
 * @description: 二叉树的堂兄弟节点
 * @date 2020/6/16 9:19
 * <p>
 * https://leetcode-cn.com/problems/cousins-in-binary-tree/
 */

import cn.hutool.core.convert.Convert;
import lombok.Data;
import lombok.extern.slf4j.Slf4j;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
@Slf4j
public class Solution {

    // 缓存深度和父节点
    public static Map<Integer, Integer> depthMap;
    public static Map<Integer, TreeNode> parentMap;

    public static void main(String[] args) {
        TreeNode root = BinaryTree.create("30,1,5,8,10,12,19,20");
        log.info("root: {}", root);
//        log.info("3,5 isCousins:{}", new Solution().isCousins(root, 3, 5));
//        log.info("5,8 isCousins:{}", new Solution().isCousins(root, 8, 5));
        log.info("5,12 isCousins:{}", new Solution().isCousins(root, 12, 5));
    }

    /**
     * 是否为堂兄弟 - 父节点不同,深度相同
     *
     * @param root
     * @param x
     * @param y
     * @return
     */
    public boolean isCousins(TreeNode root, int x, int y) {
        depthMap = new HashMap<>();
        parentMap = new HashMap<>();

        // 初始化 root ,把参数设置到缓存中
        iteratorTree(root, null);

        return depthMap.get(x) == depthMap.get(y)
                &&
                parentMap.get(x) != parentMap.get(y)
                ;
    }

    /**
     * 迭代二叉树,获取每个元素的深度和父节点,存储起来
     *
     * @param node
     */
    private void iteratorTree(TreeNode node, TreeNode parent) {
        if (node == null) {
            return;
        }
        // 深度
        depthMap.put(node.val, parent == null ? 0 : depthMap.get(parent.val) + 1);
        // 父节点
        parentMap.put(node.val, parent);
        iteratorTree(node.left, node);
        iteratorTree(node.right, node);
    }
}


/**
 * 二叉树
 */
@Data
class BinaryTree {
    TreeNode root; // 根节点

    public BinaryTree() {
        this.root = null;
    }

    public BinaryTree(TreeNode root) {
        this.root = root;
    }

    /**
     * 创建二叉树,最后返回root节点
     *
     * @param trees
     * @return
     */
    public static TreeNode create(String trees) {
        int[] treeNodes = Arrays.stream(trees.split(",")).mapToInt(x -> Convert.toInt(x)).toArray();
        List<TreeNode> nodelist = new ArrayList<>();

        //将数组变成node节点
        for (int nodeindex = 0; nodeindex < treeNodes.length; nodeindex++) {
            TreeNode node = new TreeNode(treeNodes[nodeindex]);
            nodelist.add(node);
        }

        //给所有父节点设定子节点
        for (int index = 0; index < nodelist.size() / 2 - 1; index++) {
            //编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号，所以还要+1
            //这里父节点有1（2,3）,2（4,5）,3（6,7）,4（8,9） 但是最后一个父节点有可能没有右子节点 需要单独处理
            nodelist.get(index).setLeft(nodelist.get(index * 2 + 1));
            nodelist.get(index).setRight(nodelist.get(index * 2 + 2));
        }

        //单独处理最后一个父节点 因为它有可能没有右子节点
        int index = nodelist.size() / 2 - 1;
        nodelist.get(index).setLeft(nodelist.get(index * 2 + 1)); //先设置左子节点
        if (nodelist.size() % 2 == 1) { //如果有奇数个节点，最后一个父节点才有右子节点
            nodelist.get(index).setRight(nodelist.get(index * 2 + 2));
        }

        return nodelist.get(0);
    }

    public boolean isEmpty() {
        return root == null;
    }

    public TreeNode getRoot() {
        return root;
    }

    /**
     * 获取父节点
     *
     * @param currentNode
     * @return
     */
    TreeNode getParent(TreeNode currentNode) {
        if (currentNode == null) {
            return null;
        }
        return Solution.parentMap.get(currentNode.val);
    }

}

/**
 * 二叉树节点
 */
@Data
class TreeNode {
    int val; // 值
    TreeNode left; //左节点
    TreeNode right;// 右节点

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}